Projet ISOC 731¶

Forray Gabriel & Cochard Antoine¶

https://github.com/ForrayGabriel/ISOC731¶

Installations and imports

In [ ]:
import networkx as nx
import matplotlib.pyplot as plt
import random
from typing import List  
from dataclasses import dataclass

1 - Random graph¶

This part is about creating random graphs with different probabilites and analyzing the data about the maximum number of node connected together.

In [ ]:
n = 100  # number of nodes
p = 0.1  # probability to connect with an other node

x = []
y = []

Gs = []

def generatGraph(p, ax):
    G = nx.fast_gnp_random_graph(100,p)
    Gs.append(G)
    nx.draw_networkx(G, ax=ax, node_size=150, with_labels = False)
    largest = len(sorted(nx.connected_components(G), key=len, reverse=True)[0])
    ax.set_title("Probability : " + str(p) + "\nSize of the largest connected component " + str(largest))
    ax.axis("off")
    x.append(p)
    y.append(largest)

fig, axs = plt.subplots(20,5,figsize=(35,140))

for i in range(100):
    generatGraph(i/100, axs[i//5, i%5])

We generate graphs of a 100 nodes with a certain probability p of a node beeing connected to any other nodes.
We then use this function a 100 time and variate the probability between 0.01 and 1. We can see that it quickly form big groups of nodes that are linked together.
We log the biggest group of node for each probability and trace the next graph :

In [ ]:
plt.plot(x,y)
fig = plt.gcf()
fig.set_size_inches(10, 3)
fig.legend(["Number of Nodes connected together"])
plt.xlabel("Probability p")
plt.ylabel("Largest connected component")

We can observe that quickly, from p=0.05 (5%) or p=0.06 (6%), all the nodes are connected together.

In [ ]:
def plot_degree_dist(G, ax, p):
    degrees = [G.degree(n) for n in G.nodes()]
    ax.set(xlim=(0, 100), ylim=(0, 40))
    ax.hist(degrees, bins=20)
    ax.set_title("Probability : " + str(p))

fig, axs = plt.subplots(10,10,figsize=(40,40))

i=0
for G in Gs:
    plot_degree_dist(G, axs[i//10, i%10], i/100)
    i += 1

We can observe thanks to the graphs that the average number of neighbors increase when the probability p increase too. We can see the blue shape moving from left to right when we increase the probability of each node to connect to others. So, when a node have few chances to connect himself, the average number of connections is low. At the end, when the probability is near to 1, the number of links for each node is near to the number of nodes.

2 - Simple graph formation game¶

Without interferences¶

First we create a data class for representing the node.
Each node has an ID, a value, a timing that is a random value for choosing the order in which the nodes play, an int that keep trace of whch node this node connected to, and its karma.

In [ ]:
@dataclass
class Node(object):   
    ID: int   
    Value: int  
    Timing: float
    NodeConnected: int
    Karma_tot: int
    Karma_defect: int

def findNode(list, id):
    for n in list:
        if n.ID == id:
            return n

Then we make a first version of the game that play witout interferences.
First we create 10 nodes, all with the value 0.
Then we make each node play. We search the node with the biggest value and then connect the playing node to it. If some nodes have the same maximum value, we select one randomly.

In [ ]:
def simple_game_without_interference(): 
    G = nx.Graph()

    Nodes = []

    n = 100

    # We create n nodes, each one has an id, a value initialized to 0 and a random timing value
    # Then we add them to the graph
    for i in range(n):
        node = Node(i, 0, random.random(), -1 ,0, 0)
        Nodes.append(node)
        G.add_node(i, data = Node)

    # We sort the nodes by the timing value to determine the order in which the nodes will play
    Nodes = sorted(Nodes, key=lambda x: x.Timing)

    print("First Node : ", Nodes[0])

    # For each node
    for nodePlaying in Nodes:
        # We take the node by timing order
        
        # We make a list of nodes to which the playing node can connect (every node except him)
        index = Nodes.index(nodePlaying)
        selectableNodes = Nodes[:index]+ Nodes[index+1:]

        # We search for the maximum value in any nodes
        maxValue = max(selectableNodes, key = lambda node:node.Value).Value

        # If the max value is 0, there are no connections
        if maxValue == 0:
            # We get a random node
            nodeRandom = random.choice(selectableNodes)

            print("First random Node : ", nodeRandom)

            # We make the connection between the randomly selected node and the one with the lowest timing and set their values to 1
            G.add_edge(nodePlaying.ID, nodeRandom.ID)
            nodePlaying.Value = 1
            nodeRandom.Value = 1
        
        else:
            # We make a list of nodes that have the maximum value
            listMaxNodes = []
            for n in selectableNodes:
                if n.Value == maxValue:
                    listMaxNodes.append(n)
            
            # We select a random node between them
            nodeToConnect = random.choice(listMaxNodes)

            # If the nodes are not already connected, we connect them and increase their values
            if G.has_edge(nodePlaying.ID,nodeToConnect.ID) == False :

                G.add_edge(nodePlaying.ID, nodeToConnect.ID)
                
                nodeToConnect.Value+=1
                nodePlaying.Value+=1



    nx.draw_networkx(G,node_color=range(100))

simple_game_without_interference()

First Node :  Node(ID=22, Value=0, Timing=0.004212448832652593, NodeConnected=-1, Karma_tot=0, Karma_defect=0)
First random Node :  Node(ID=28, Value=0, Timing=0.29505978277714673, NodeConnected=-1, Karma_tot=0, Karma_defect=0)

We can see that in every simulations, there is always one node in the center with all the other nodes connected to it. It is always either be the node with the lowest timing or the first randomnlly choosed Node.
It is like that because, when the second Node is playing, they are the only two other nodes with a value of 1 instead of 0. The second Node will randomnly choose one of the two, increasing its value. Then this node will always be selected and increased at each step. This strategy take the most powerful node and incraese its value at every rounds.

With interferences¶

In this part, we will play the same game, but when they search for the best node, their are interferences that change the value of the analyzed node.
This time we create a 100 nodes. When searching for the maximum node we search for a maximum. During ths search, the value of the analyzed node is multiplied by a random number between two values.

In [ ]:
def simple_game_with_interference(ax, interference, iteration):
    G = nx.Graph()

    Nodes = []

    n = 100

    # We create n nodes, each one has an id, a value initialized to 0 and a random timing value
    # Then we add them to the graph
    for i in range(n):
        #node = Node(i, 0, random.random(), -1, 1)
        node = Node(i, 0, i/100, -1, 0,0)
        Nodes.append(node)
        G.add_node(i)

    # We sort the nodes by the timing value to determine the order in which the nodes will play
    Nodes = sorted(Nodes, key=lambda x: x.Timing)

    first = "First Node : " +  str(Nodes[0].ID)

    # For each node
    for nodePlaying in Nodes:
        # We take the node by timing order
        
        # We make a list of nodes to which the playing node can connect (every node except him)
        index = Nodes.index(nodePlaying)
        selectableNodes = Nodes[:index]+ Nodes[index+1:]

        # We search for the maximum value in any nodes
        maxValue = max(selectableNodes, key = lambda node:node.Value).Value

        # If the max value is 0, there are no connections
        if maxValue == 0:
            # We get a random node
            nodeRandom = random.choice(selectableNodes)

            # We make the connection between the randomly selected node and the one with the lowest timing and set their values to 1
            G.add_edge(nodePlaying.ID, nodeRandom.ID)
            nodePlaying.NodeConnected = nodeRandom.ID
            nodePlaying.Value = 1
            nodeRandom.Value = 1
        
        else:
            #Searching for the Node with the maximum vizible value
            nodeToConnect = None
            maxValue = 0
            for n in selectableNodes:
                #Wwhen looking for the value, modifying it with the interferences
                interferedValue = n.Value*random.randint(100-interference,100+interference*10000)/100
                if interferedValue > maxValue:
                    maxValue = interferedValue
                    nodeToConnect = n

            nodePlaying.NodeConnected = nodeToConnect.ID


            # If the nodes are not already connected, we connect them and increase their values
            if G.has_edge(nodePlaying.ID,nodeToConnect.ID) == False :

                G.add_edge(nodePlaying.ID, nodeToConnect.ID)

                nodeToConnect.Value+=1
                nodePlaying.Value+=1

    # Search for the maximum value node to color him differently
    maxNode = None
    maxValue = 0
    for n in Nodes:
        if n.Value>maxValue:
            maxNode = n
            maxValue = n.Value
    colorMap = []
    color = 17
    for n in Nodes:
        if n.ID == maxNode.ID:
            colorMap.append('#48EB00')
        else :
            if iteration%2 == 0:
                colorMap.append('#76519E')
            else :
                colorMap.append('#EB110C')
           
    nx.draw_networkx(G, node_color=colorMap, ax=ax, node_size=150, with_labels = False)    
    ax.axis('off')   
    return G, Nodes

We then make multiples simulation to have different results.

In [ ]:
fig, axs = plt.subplots(3,3,figsize=(20,20))

fig.suptitle("9 random generations of one round\nThe Green point is the node with the maximum value", fontsize=25)

for i in range(9):
    simple_game_with_interference(axs[i//3, i%3], 80, i)

Some of these graph are really intresting.
As we can see, most of these graph are articulated around 2 main nodes. These 2 nodes are the ones that connect in the beggining and have the highest value. Thanks to the interferences, a playing node can see the lowest of the two as bigger and connect to it. These two nodes will see their values increase in parallele and be both attractive for the other nodes, until one of the two outgrow the other and become more attractive for the other nodes, even with the interferences, and get a lot more connections.

3 - More advanced graph formation game¶

In this part, we create a function that play an other round with the same graph and nodes.
In the same order than before, each node will play.
When it plays, a node will look for the node with the biggest value. If this value is bigger than te current node it is already connected to,it disconnect and try to connect to the new one. But it will not succeed to reconnect every time. Each node has a karma value that is equal to the number of time it disconnected divided by the number of time it played.

In [ ]:
def find_node(Nodes, ID):
    for n in Nodes:
        if n.ID == ID:
            return n
    return Node(-1, -100, i/100, -1, 0,0)
In [ ]:
def next_round(ax, interference, G, Nodes, iteration):
    
    # For each node
    for nodePlaying in Nodes:
        # We take the node by timing order
        # We make a list of nodes to which the playing node can connect (every node except him)
        index = Nodes.index(nodePlaying)
        selectableNodes = Nodes[:index]+ Nodes[index+1:]

        nodePlaying.Karma_tot +=1
        #Searching for the Node with the maximum vizible value
        nodeToConnect = Node(i, 0, i/100, -100, 0,0)
        maxValue = 0
        for n in selectableNodes:
            #Wwhen looking for the value, modifying it with the interferences
            interferedValue = n.Value*random.randint(100-interference,100+interference*1000)/100
            if interferedValue > maxValue:
                maxValue = interferedValue
                nodeToConnect = n
        
        
        # Finding the node which we are already connected to
        node_already_connected = find_node(Nodes, nodePlaying.NodeConnected)
        # If another node as a greater value
        if node_already_connected.Value < nodeToConnect.Value:
            # We disconnect it from the node its already connected to
            if G.has_edge(nodePlaying.ID, node_already_connected.ID):
                G.remove_edge(nodePlaying.ID, node_already_connected.ID)
            
                nodePlaying.Value -= 1
            
                # Then we increase its karma
                # Having a greater karma is actually bad
                nodePlaying.Karma_defect +=1

            # We compare the karma to a random number, if it's lower, the node can reconnect
            rand = random.random()
            if nodePlaying.Karma_defect/nodePlaying.Karma_tot < rand:
                
                # We connect the two nodes and increase their values
                G.add_edge(nodePlaying.ID, nodeToConnect.ID)
                nodePlaying.NodeConnected = nodeToConnect.ID

                nodeToConnect.Value+=1
                nodePlaying.Value+=1
                
            else :
                nodePlaying.NodeConnected = -1
                nodePlaying.Value=0


    
    # We search and color the nodes            
    maxNode = None
    maxValue = 0
    for n in Nodes:
        if n.Value>maxValue:
            maxNode = n
            maxValue = n.Value
    colorMap = []
    color = 0
    for n in Nodes:
        if n.ID == maxNode.ID:
            colorMap.append(200)
        else :
            colorMap.append(color)
            color +=1

    
    
    nx.draw_networkx(G, node_color=colorMap, ax=ax, node_size=150, with_labels = False)
    largest = len(sorted(nx.connected_components(G), key=len, reverse=True)[0])
    ax.set_title("Iteration number : " + str(iteration) +"\nSize of the largest connected\ncomponent :" + str(largest), fontsize=15)
    ax.axis('off')
    return G, Nodes

We play a first round as usual, then 8 other round where the node can disconnect.

In [ ]:
fig, axs = plt.subplots(3,3,figsize=(20,20))

interference=99

G, Nodes = simple_game_with_interference(axs[0,0],80, 1)

fig.suptitle("A first generation, then 8 rounds of the game\nThe Yellow point is the node with the maximum value", fontsize=25)

for i in range(1,9):
    G, Nodes = next_round(axs[i//3,i%3],interference, G, Nodes, i)

As we can see in the graph, in the first round, two nodes where bigger than the other.
In the first iteration, some nodes where not connected to one of the two pricipal nodes, and saw the orther one as bigger. So the disconnected. They had 1/1 chance of not being connected and are left alone.
In the second round, some nodes tryed and succeed to connect to the other principal node. Other werre disconnected and left alone. And some of the alone nodes reconnected to the biggest node.
With more and more rounds, more and more nodes switched to the biggest node and, as they disconnected less comparing to the number of time they played.
In the end all the nodes are connected to the biggest node.